import java.util.*;

public class Practice1 {
    //https://leetcode.cn/problems/uUsW3B/description/
    //dfs搜索
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    int t;
    int length;
    public List<List<Integer>> combine(int n, int k) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[k];
        t = n;
        length = k;
        dfs(0,1);
        return ret;
    }
    public void dfs(int n, int pos){
        if(path.size() == length){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = pos;i <= t;i++){
            if(check[n] == false){
                path.add(i);
                check[n] = true;
                dfs(n + 1,i + 1);
                check[n] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
